package com.lili.sort;

/**
 * @Auther: 李 力
 * @Date: 2024/8/2
 * @Description: 数组的相对排序
 * @version: 1.0
 */
public class LeetCode1122 {
    /*
     * 思路: 计数排序实现
     * 时间复杂度: O(arr1.len+arr2.len+arr1的最大值)
     * 空间复杂度: O(arr1的最大值)
     */
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        int[] count = new int[1001];
        for (int i : arr1) {
            count[i]++;
        }
        int[] result = new int[arr1.length];
        int k = 0;
        //arr2中的元素当成是count数组的元素
        for (int i : arr2) {
            while (count[i] > 0) {
                result[k] = i;
                count[i]--;
                k++;
            }
        }
        //处理arr1中在arr2中没有出现的元素
        for (int i = 0; i < count.length; i++) {
            while (count[i] > 0) {
                result[k] = i;
                count[i]--;
                k++;
            }
        }
        return result;
    }
}
